/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 05 - 22
 * Time: 10:47
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Practice {
        public ListNode partition(ListNode pHead, int x) {
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;
            ListNode cur = pHead;
            while(cur != null) {
                if(cur.val < x) {
                    if(bs == null) {
                        bs = be = cur;
                    }
                    be.next = cur;
                    be = be.next;
                }else {
                    if(as == null) {
                        as = ae = cur;
                    }
                    ae.next = cur;
                    ae = ae.next;
                }
                cur = cur.next;
            }
            if(bs == null) {
                return as;
            }
            if(ae.next != null) {
                ae.next = null;
            }
            be.next = as;
            return bs;
        }

}
